﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once//作用：防止头文件重复包含，以后尽量都写上
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//以后写项目文件添加都要直接从项目里添加，更保险



//定义链式二叉树结构
//定义二叉树结点结构
typedef char BTDataType;
typedef struct BinaryTreeNode {
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;


//前序遍历--根左右
void PreOrder(BTNode* root);
//中序遍历--左根右
void InOrder(BTNode* root);
//后序遍历--左右根
void PostOrder(BTNode* root);


// ⼆叉树结点个数
//void BinaryTreeSize(BTNode* root,int*psize);
int BinaryTreeSize(BTNode* root);
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);
//⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);

//层序遍历
//遍历顺序：A B C D E F
//层序遍历是广度优先遍历，递归一定是深度优先遍历（从上往下，然后再回溯）
//思路：借助数据结构--队列，根结点入队列，循环判断队列是否为空
//不为空取队头出队头，将队头的左右且不为空的孩子入队列
void LevelOrder(BTNode* root);

//判断是否为完全二叉树
//层序遍历，根结点入队列，循环判断队列是否为空
//不为空取队头出队头，将队头的左右孩子入队列，不管是不是空
//遇到空停止循环，比较队列剩余元素，
//如果还有非空元素，则为非完全二叉树，反之是完全二叉树
bool BinaryTreeComplete(BTNode* root);
